#include <iostream>
#include <vector>
using namespace std;


class Solution {
public:

    // 518. 零钱兑换 II
    // https://leetcode.cn/problems/coin-change-ii/
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<int> dp(amount+1);
        dp[0] = 1;

        for (int i = 1; i<=n; ++i)
        {
            for (int j = coins[i-1]; j<=amount; ++j)
            {
                dp[j] += dp[j-coins[i-1]];
            }
        }

        return dp[amount];
    }

    // 279. 完全平方数
    // https://leetcode.cn/problems/perfect-squares/
    int numSquares(int n) {
        int INF = 0x5f5f5f5f;
        vector<int> dp(n+1, INF);
        dp[0] = 0;
        int m = sqrt(n);

        for (int i = 1; i<=m; ++i)
        {
            for (int j = i*i; j<=n; ++j)
            {
                dp[j] = min(dp[j], dp[j-i*i]+1);
            }
        }

        return dp[n];
    }
};